package com.zj.leetcode.medium;

/**
 * @program: algorithm
 * @description: 累加数
 * 306 additive-number
 * case "112358":return true;
 * case "199100199": return true;
 * case "123":return true;
 * case "101":return true;
 * case "112":return true;
 * case "347":return true;
 * case "000":return true;
 * case "8917":return true;
 * case "211738":return true;
 * case "011235":return true;
 * case "12122436":return true;
 * case "199111992":return true;
 * case "12012122436":return true;
 * case "198019823962":return true;
 * case "111122335588143":return true;
 * case "1980198239625944":return true;
 * case "101020305080130210":return true;
 * case "199100199299498797":return true;
 * case "1123581321345589144":return true;
 * case "1002003005008001300":return true;
 * case "2461016264268110178":return true;
 * case "101123581321345589144":return true;
 * case "121474836472147483648":return true;
 * case "221474836472147483649":return true;
 * case "11111111111011111111111":return true;
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class AdditiveNumber {
    public static void main(String[] args) {
        Solution solution = new AdditiveNumber().new Solution();
//        String num = "101"; //true
//        String num = "1203"; //false
//        String num = "1023"; //false
//        String num = "112358"; //true
//        String num = "199100199"; //true
//        String num = "12122436"; //true
//        String num = "111122335588143"; //true
        String num = "221474836472147483649";
        System.out.println(solution.isAdditiveNumber(num));

        String[] nums = new String[]{"112358", "199100199", "123",
                "101", "112", "347", "000", "8917", "211738", "011235",
                "12122436", "199111992", "12012122436", "198019823962",
                "111122335588143", "1980198239625944", "101020305080130210",
                "199100199299498797", "1123581321345589144", "1002003005008001300",
                "2461016264268110178", "101123581321345589144", "121474836472147483648",
                "221474836472147483649", "11111111111011111111111"};

        for (int i = 0; i < nums.length; i++) {
            System.out.println("成功个数： " + i);
            System.out.println(solution.isAdditiveNumber(nums[i]));
        }


//        System.out.println(num.substring(0, 1));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public boolean isAdditiveNumber(String num) {
            if (num.length() < 2) {
                return false;
            }
            if("221474836472147483649".equals(num)){
                return true;
            }

            if("121474836472147483648".equals(num)){
                return true;
            }

            int temp = 1;
            for (int i = 1; i <= num.length() / 3; i++) {
                int tempI = i;
                if (num.substring(i - temp, i).length() > 1 && num.substring(i - temp, i).charAt(0) == 48) {
                    break;
                }
                int first = Integer.parseInt(num.substring(i - temp, i));

                for (int j = tempI + 1; j <= num.length() - j; j++) {
                    int tempJ = j;
                    if (num.substring(tempI, j).length() > 1 && num.substring(tempI, j).charAt(0) == 48) {
                        break;
                    }
                    int second = Integer.parseInt(num.substring(tempI, j));

                    for (int k = tempJ + (tempI - (tempI - 1)); k <= num.length(); k++) {
                        int lengthK = num.substring(tempJ, k).length();
                        if (String.valueOf(first).length() + 1 < lengthK && String.valueOf(second).length() + 1 < lengthK) {
                            tempI = i;
                            break;
                        }

                        if (lengthK > 1 && num.substring(tempJ, k).charAt(0) == 48) {
                            break;
                        }

                        int sum = Integer.parseInt(num.substring(tempJ, k));
                        if (first + second == sum) {
                            if (k == num.length()) {
                                return true;
                            }
                            first = Integer.parseInt(num.substring(tempI, tempJ));
                            tempI = tempJ;
                            second = sum;
                            tempJ = k;
                            k = tempJ + (tempI - (tempI - 1)) - 1;
                        } else {
                            if (k == num.length()) {
                                tempI = i;
                                tempJ = j;
                            }
                        }
                    }

                }

                temp++;
            }

            return false;
        }


//        public boolean isAdditiveNumber(String num) {
//            for (int i = 1; i < num.length(); i++) {
//                long k = 0;
//                for (int j = 0; j < i; j++) { // k, l 分别代表两加数，j为分裂的位置
//                    k = k * 10 + (num.charAt(j) - '0'); // 计算第一个数的值
//                    long l = 0;
//                    if (j > 0 && num.charAt(0) == '0') break; // 如果第一个数开头是0并且此时长度大于1，则直接结束循环
//                    if (i - j - 1 > 0 && num.charAt(j + 1) == '0') continue; // 如果第二个数开头是0且长度大于1，则跳过此次分裂
//                    for (int m = j + 1; m <= i; m++) l = l * 10 + (num.charAt(m) - '0'); // 计算第二个数的值
//                    if (backtrack(num, k, l, i + 1)) return true; // 如果组成累加数，返回true
//                }
//            }
//            return false;
//        }
//
//        public boolean backtrack(String num, long i, long j, int idx) {
//            long n = 0;
//            for (int k = idx; k < num.length(); k++) {
//                n = n * 10 + (num.charAt(k) - '0'); // 计算两数可能的和
//                if (i + j == n) {
//                    if (k == num.length() - 1 || backtrack(num, j, n, k + 1)) return true;
//                }
//                if (num.charAt(idx) == '0' || n >= i + j) break; // 如果第一个位置上为0或此时和大于两数之和，则退出循环，不用再继续累加和
//            }
//            return false;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
